// The main class is Grammar, which has the list of Rules. A Rule is a list of
// Token pointers, which can either be Terminals or Nonterminals.

#include <assert.h>
#include <stdio.h>
#include <string.h>

#include <algorithm>
#include <iostream>
#include <iterator>
#include <fstream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

using namespace std;


// Forward decls.
class Grammar;
class Rule;


// Exception class.
class ParseGrammarException {
  string why;
  
public:
  inline ParseGrammarException(const string &in_why) : why(in_why) {}
  
  inline const string &get_why() const { return why; }
};

// Kind of like an enum of all terminals.
// class TerminalType {
//   
// // TerminalType TERMINALS[] = {
// //   LEFTPAR, RIGHTPAR, ASSIGN, COMMA, 
// //   SEMICOLON, PLUS, MINUS, MULTIPLY, 
// //   MODULO, BEGIN, END, PRINT, READ
// // };
// 
//   // Private map of names to terminals. Used when parsing .
//   static map<string, TerminalType> all_terminals;
//   
// public:
//   
//   // Keyword name, 'LEFTPAR', 'RIGHPAR', etc.
//   string name;
//   
//   // The actual string representation. Doesn't make sense for INTNUM, ID.
//   string str;
//   
//   inline TerminalType() {}
//   TerminalType(const string &in_name, const string &in_str);
//   
//   inline const string &get_name() { return name; }
//   inline const string &get_str() { return str; }
//   
//   static const TerminalType &find(const string &name);
//   
// };
// 
// inline bool operator==(const TerminalType &a, const TerminalType &b) { return a.name == b.name; }

class Token {
  
protected:
  Grammar *grammar;
  
public:
  
  inline Token(Grammar *g) : grammar(g) {}
  Grammar* get_grammar() const {return grammar; }
  virtual bool is_terminal() const = 0;
  virtual string get_name() const = 0;
  
};

class Terminal : public Token {

public:
  
  string name;
  
  inline Terminal(Grammar *g, const string &in_name) : Token(g), name(in_name) {}
  
  bool is_terminal() const { return true; }
  
  string get_name() const { return name; }
};

class Nonterminal : public Token {
  
  
public:
  
  string name;
  // Each rule has one nonterminal and a list of tokens.
  vector<Rule*> rules;

  //Following introduced for easier and cleaner way to code table construction
  map<Token*, vector<Rule*> > follow;
  map<Token*, vector<Rule*> > predict;
  void print_first();
  void print_follow();
  void print_predict();
  bool token_pair_in_follow(Token* t, Rule* r);
  inline Nonterminal(Grammar *g, const string &in_name) : Token(g), name(in_name) {}
  ~Nonterminal();
  
  bool is_terminal() const { return false; }

  void print_self();
  bool token_in_first(Token *t);
  bool token_in_follow(Token *t);
  bool token_pair_in_predict(Token *t, Rule *r);
  void follow_to_predict();
  void predict_to_table(Grammar *g);
  string get_name() const { return name; }
  bool copy_first(Rule *r);
  bool create_left_factoring();
  bool follow_to_follow(Nonterminal *nt);
  bool first_to_follow(Nonterminal *nt);
};

class Rule {
  
  Grammar *grammar;
  
public:
  
  // Might as well just make these public.
  
  // The nonterminal this rule produces.
  Nonterminal *produces;

  // The list of tokens for this rule.
  vector<Token*> tokens;
  
  //All the tokens in the first set of this production rule
  vector<Token*> first;

  inline Rule(Grammar *g, Nonterminal *in_produces) : grammar(g), produces(in_produces) {
    produces->rules.push_back(this);
  }
  bool token_in_first(Token *t);
  void first_to_predict(Nonterminal *nt);
};

class Grammar {
  
  friend class GrammarParser;

public:  
  Nonterminal *start;

  // Parsing table. 2D array-like, maps (Nonterminal, Terminal) to a Rule. See
  // get_parsing_table_entry().
  // map<Nonterminal*, map<string, Rule*> > parsing_table;//string is Terminal.tt.name
  //map<Nonterminal*, vector<Token*> > first, follow, predict;


public:

  map<string, Terminal*> terminals;
  map<string, Nonterminal*> nonterminals;
  map<Nonterminal*, map<Terminal*, vector<Rule*> > > table;
  string get_epsilon_name() const {return "{EPSILON}";}
  Token *get_epsilon();  
  inline Grammar() {}
  void construct_first();
  void construct_follow();
  void construct_table();
  void construct_predict();
  void print_table_to_file();
  void assemble();
  void debug();
  ~Grammar();


  void remove_left_recursion();
  void create_left_factoring();
  void print_rules();
	
  // Not const b/c of the way maps work.
  Rule *get_parsing_table_entry(Nonterminal *N, const string &T);
  
  void dump_parsing_table(ostream &out) const;
  
};

class GrammarParser {
  
  friend class Grammar;
  
  istream *in;
  Grammar g;

  // Reads str exactly or throws an exception.
  void expect(const string &str);

  // Skips space char
  void skip_ws();
  
  // Skips ws up to newline. Consumes newline.
  void skip_newline();

  // Reads <Non-terminal id>, returns "Non-terminal id"
  string read_nonterminal_id();
  
  // Reads SOMETHING, returns "SOMETHING"
  string read_terminal_id();
  
  void parse_tokens();
  void parse_nonterminals(); 
  void parse_start(); 
  void parse_rules_intro(); 
  void parse_rule_line(); 
  
public:
  
  GrammarParser();
  
  void parse(istream *in);

  inline Grammar &get_g() { return g; }
  
};


// map<string, TerminalType> TerminalType::all_terminals;
// 
// TerminalType LEFTPAR("LEFTPAR", "(");
// TerminalType RIGHTPAR("RIGHTPAR", "(");
// TerminalType ASSIGN("ASSIGN", "=");
// TerminalType COMMA("COMMA", ",");
// TerminalType SEMICOLON("SEMICOLON", ";");
// TerminalType PLUS("PLUS", "+");
// TerminalType MINUS("MINUS", "-");
// TerminalType MULTIPLY("MULTIPLY", "*");
// TerminalType MODULO("MODULO", "%");
// TerminalType BEGIN("BEGIN", "begin");
// TerminalType END("END", "end");
// TerminalType PRINT("PRINT", "print");
// TerminalType READ("READ", "read");
// TerminalType INTNUM("INTNUM", "???");
// TerminalType ID("ID", "???");


// TerminalType::TerminalType(const string &in_name, const string &in_str) {
//   name = in_name;
//   str = in_str;
//   
//   // Add ourselves to the list of all terminals.
//   all_terminals[name] = *this;
// }
// 
// const TerminalType &TerminalType::find(const string &name) {
//   return all_terminals[name];
// }
// 

Nonterminal::~Nonterminal() {
  for (vector<Rule*>::iterator it = rules.begin(); it < rules.end(); it++)
    delete *it;
}

Grammar::~Grammar() {
  for (map<string, Terminal*>::iterator it = terminals.begin(); it != terminals.end(); it++)
    delete it->second;
    
  for (map<string, Nonterminal*>::iterator it = nonterminals.begin(); it != nonterminals.end(); it++)
    delete it->second;
    
}

//Copies all token*/rule* pairs from first to predict if not in predict
void Rule::first_to_predict(Nonterminal *nt){
  vector<Token*>::iterator it;
  for(it = first.begin(); it != first.end(); it++){
    if(!(nt->token_pair_in_predict(*it, this))){
      nt->predict[*it].push_back(this);
      cout << "\nADDED (" << (*it)->get_name() << " , " << this->produces->get_name() << ") to predict " << nt->get_name();
    }
  }
}



Token *Grammar::get_epsilon(){
  string eps = get_epsilon_name();
  //  cout << "\nGetting eps:" << eps;
  //  cout << "\n" << terminals[eps];
  return terminals[get_epsilon_name()];
}


void Grammar::remove_left_recursion()
{
  //cout << "RLR: Retrieving keys..." << endl;
  vector<string> keys;
  for(map<string, Nonterminal*>::iterator iter = nonterminals.begin();iter!=nonterminals.end();iter++)
  {
    keys.push_back(iter->first);
  }
  //cout << "RLR: Iterating through Nonterminals (" << (int)keys.size() << ")..." << endl;
  /*Iterating through initial nonterminals*/
	for(int i=0;i<(int)keys.size();i++)
	{
    //cout << "RLR: Evaluating nonterminal at index: " << i << endl;
		bool recursionfound = false;
		Nonterminal *newnterminal = new Nonterminal(this,((nonterminals[keys[i]])->name) + "-recur");
    //cout << "RLR: Newn: " << newnterminal << endl;
    //newnterminal->print_self();
		vector<Rule*> *currrules = &((nonterminals[keys[i]])->rules);
    /*Iterating through all Rules listed with the current nonterminal*/
		for(int j=0;j<(int)currrules->size();j++)
		{
      /*Checking for left recursion*/
			if(((*currrules)[j])->tokens[0]==(((*currrules)[j])->produces))
			{
        //cout << "RLR: Recursion found at index: " << j << endl;
				recursionfound = true;
        /*Adding recursive rule to newnterminal*/
				(newnterminal->rules).push_back((*currrules)[j]);
        //cout << "RLR: Newn after adding rule: " << endl << "        ";
        //newnterminal->print_self();
        vector<Rule*>::iterator iterA = currrules->begin();
        /*Erasing recursive rule from current nonterminal*/
				currrules->erase((currrules->begin())+j);
        //cout << "RLR: Currrules after erase: " << endl << "        ";
        //(nonterminals[keys[i]])->print_self();
        //((nonterminals[keys[i]])->rules).erase((currrules->begin())+j);
        vector<Token*>::iterator iterB = ((*((newnterminal->rules).back())).tokens).begin();
        /*Editing shifted rules to remove left recursion*/
				((*((newnterminal->rules).back())).tokens).erase(iterB);
				((*((newnterminal->rules).back())).tokens).push_back(newnterminal);
        //cout << "RLR: Newn after reformatting: " << endl << "        ";
        //newnterminal->print_self();
				j = j - 1;
        //cout << "RLR: Remaining size: " << (int)currrules->size() << endl;
			}
		}
		if(recursionfound==true)
		{
      //cout << "RLR: Checking for indirect left recursion..." << endl;
      //cout << "RLR:   > Adding empty string..." << endl;
      /*Adding empty string to newnterminal*/
      
      // Create an empty rule.
      new Rule(this,newnterminal);
      
      /*cout << "RLR: Newn after adding empty string: " << endl << "        ";
      newnterminal->print_self();*/
      //cout << "RLR:   > Adding new Nonterminal..." << endl;
      /*Adding newnterminal to all remaining rules in current nonterminal*/
      for(int j=0;j<(int)currrules->size();j++)
			{
				(((*currrules)[j])->tokens).push_back(newnterminal);
        //cout << "RLR: Currrules after reformatting: " << endl << "        ";
        //(nonterminals[keys[i]])->print_self();
			}
      /*Adding newnterminal to map nonterminals*/
      //cout << "RLR:   > Inserting pair (" << newnterminal->name << "," << newnterminal << ")..." << endl;
			nonterminals.insert(pair<string,Nonterminal*>(newnterminal->name,newnterminal));
      /*cout << "RLR:   > Retrieving new keys..." << endl;
      vector<string> tempkeys;
      for(map<string, Nonterminal*>::iterator iter = nonterminals.begin();iter!=nonterminals.end();iter++)
      {
        tempkeys.push_back(iter->first);
      }*/
      //cout << "RLR:   > Iterating through Nonterminals (" << (int)nonterminals.size() << ")..." << endl;
      /*Iterating through other nonterminals to check for indirect left recursion*/
			for(int j=0;j<(int)keys.size();j++)
			{
				if(i!=j)
				{
					vector<Rule*> temprules = (nonterminals[keys[j]])->rules;
					for(int k=0;k<(int)temprules.size();k++)
					{
            /*Checking for left recursion*/
						if((temprules[k])->tokens[0]==((*currrules)[0]->produces))
						{
              //cout << "RLR:   > Recursion found!" << endl;
              /*Removing indirect left recursion instances*/
							for(int a=0;a<(int)currrules->size();a++)
							{
								Rule newrule = *(*currrules)[a];
								for(int b=0;b<(int)((temprules[k])->tokens.size());b++)
								{
									(newrule.tokens).push_back((temprules[k])->tokens[b]);
								}
								temprules.push_back(&newrule);
							}
              vector<Rule*>::iterator iterA = temprules.begin();
							temprules.erase(temprules.begin()+k);
							k = k - 1;
						}
					}
				}
			}
		}
    //cout << "RLR: Nonterminal evaluated" << endl;
	}
}

void Grammar::create_left_factoring() {
  bool looping = true;
  
  while (looping) {
    looping = false;
    map<string, Nonterminal*> copy_of_nonterminals = nonterminals;
    for (map<string, Nonterminal*>::iterator a = copy_of_nonterminals.begin(); a != copy_of_nonterminals.end(); a++) {
      looping |= a->second->create_left_factoring();
    }
  }
  
}

void Grammar::print_rules()
{
  
  for (map<string, Nonterminal*>::iterator nt = nonterminals.begin(); nt != nonterminals.end(); nt++) {
    cout << nt->first << ": ";
    for (vector<Rule*>::iterator rule = nt->second->rules.begin(); rule != nt->second->rules.end(); rule++) {
      if (rule != nt->second->rules.begin())
        cout << "| ";
        
      if ((*rule)->tokens.size()) {
        for (vector<Token*>::iterator token = (*rule)->tokens.begin(); token != (*rule)->tokens.end(); token++)
          cout << (*token)->get_name() << " ";
      } else {
        cout << "{empty} "; // ε
      }
    }
    cout  << endl;
  }
  
  //   vector<string> keys;
  //   for(map<string, Nonterminal*>::iterator iter = nonterminals.begin();iter!=nonterminals.end();iter++)
  //   {
  //     keys.push_back(iter->first);
  //   }
  // for(int i=0;i<(int)keys.size();i++)
  // {
  //  vector<Rule*> *currrules = &((nonterminals[keys[i]])->rules);
  //     cout << "(" << (int)currrules->size() << ")" << (nonterminals[keys[i]])->name << " -> ";
  //  for(int j=0;j<(int)currrules->size();j++)
  //  {
  //    for(int k=0;k<(int)(((*currrules)[j])->tokens).size();k++)
  //       {
  //         cout << (((*currrules)[j])->tokens[k]);
  //       }
  //       cout << "|";
  //     }
  //     cout << endl;
  //   }
}

void Nonterminal::print_self()
{
  cout << " : (" << rules.size() << ")" << name << " -> ";
  for(int i=0;i<(int)rules.size();i++)
  {
    for(int j=0;j<(int)(rules[i]->tokens).size();j++)
    {
      cout << rules[i]->tokens[j];
    }
     cout << "|";
  }
  cout << endl;
}

bool Nonterminal::create_left_factoring() {
  
  // Find largest prefix.
  vector<Token*> largest_prefix;
  for (vector<Rule*>::iterator rule1 = rules.begin(); rule1 != rules.end(); rule1++) {
    for (vector<Rule*>::iterator rule2 = rule1 + 1; rule2 != rules.end(); rule2++) {
      
      // Search for a prefix.
      size_t prefix_len = 0;
      for (size_t i = 0; i < (*rule1)->tokens.size() && i < (*rule2)->tokens.size(); i++) {
        if ((*rule1)->tokens[i] == (*rule2)->tokens[i])
          prefix_len++;
        else
          break;
      }
      
      if (prefix_len > largest_prefix.size()) {
        // If we found one, copy the tokens.
        // And start keeping track of rules w/ the given prefix.
        largest_prefix.clear(); //?
        largest_prefix.assign((*rule1)->tokens.begin(), 
          (*rule1)->tokens.begin() + prefix_len);
      } 
    }
  }
  
  if (largest_prefix.size() == 0)
    return false;
  
  // cout << "Removing largest prefix:";
  // for (vector<Token*>::iterator token = largest_prefix.begin(); token != largest_prefix.end(); token++)
  //   cout << " " << (*token)->get_name();
  // cout << endl;
  
  // Search for all rules that start with prefix.
  vector<Rule*> victims;
  for (vector<Rule*>::iterator rule = rules.begin(); rule != rules.end(); rule++) {
    if ((*rule)->tokens.size() < largest_prefix.size())
      continue;
      
    bool has_prefix = true;
    for (size_t i = 0; i < largest_prefix.size() && has_prefix; i++) {
      if ((*rule)->tokens[i] != largest_prefix[i])
        has_prefix = false;
    }
    if (has_prefix)
      victims.push_back(*rule);
  }
  
  assert(victims.size());
  
  Nonterminal *aprime = new Nonterminal(this->grammar, name + "-fac");
  // Fixme - this is inconsistent w/ Rule. Since Rule adds itself to its 
  // parent, so should Nonterminal.
  this->grammar->nonterminals[aprime->name] = aprime;

  // A -> a A'
  Rule *factored_rule = new Rule(this->grammar, this);
  factored_rule->tokens = largest_prefix;
  factored_rule->tokens.push_back(aprime);

  // Create all the rules in A'.
  for (vector<Rule*>::iterator rule = victims.begin(); rule != victims.end(); rule++) {
    rules.erase(find(rules.begin(), rules.end(), *rule)); // Take it out of A.
    Rule *aprime_rule = new Rule(this->grammar, aprime);
    // Copy all the stuff after the longest prefix.
    aprime_rule->tokens.assign((*rule)->tokens.begin() + largest_prefix.size(), (*rule)->tokens.end());
  }
  
  return true;
}

///////////////////
//Start Rowe's Code
///////////////////

bool Nonterminal::token_pair_in_follow(Token* t, Rule* r){
  map<Token*, vector<Rule*> >::iterator im;
  vector<Rule*>::iterator ir;
  if((im = follow.find(t)) != follow.end()){
    for(ir = (*im).second.begin(); ir != (*im).second.end(); ir++){
      if(*ir == r){
	return true;
      }
    }
  }
  return false;
}

bool Rule::token_in_first(Token *t){
  vector<Token*>::iterator it;
  
  for(it = first.begin(); it != first.end(); it++){
    if(*it == t){
      return true;
    }
  }
  return false;
}

bool Nonterminal::token_in_first(Token *t){
  vector<Rule*>::iterator ir;

  for(ir = rules.begin(); ir != rules.end(); ir++){
    if((*ir)->token_in_first(t)){
      cout << "\n" << t->get_name() << " in first:" << get_name();
      return true;
    }
  }
  //  cout << "\n" << t->get_name() << " not in first:" << get_name();
  return false;
}

bool Nonterminal::token_in_follow(Token *t){
  if(this->follow.find(t) == this->follow.end()){
    cout << "\nToken: " << t->get_name() << " not in follow: " << get_name();
    return false;
  }
  cout << "\nToken: " << t->get_name() << " already in follow: " << get_name();
  return true;
}

//Checks if pair is in this predict set
bool Nonterminal::token_pair_in_predict(Token *t, Rule *r){
  map<Token*, vector<Rule*> >::iterator it;
  vector<Rule*>::iterator ir;

  if((it = this->follow.find(t)) != this->follow.end()){
    //has to find token AND rule
    for(ir = (*it).second.begin(); ir != (*it).second.end(); ir++){
      if(*ir == r){
	cout << endl << t->get_name() << "->" << r->produces->get_name() << " already in predict:" << get_name();
	return true;
      }
    }
  }
  // cout << endl << t->get_name() << "->" << r->produces->get_name() << " not in predict:" << get_name();
  return false;
}

//Copy first of this to nt's follow
bool Nonterminal::first_to_follow(Nonterminal *nt){
  //map<Token*, vector<Rule*> >::iterator im;
  map<Token*, vector<Rule*> >::iterator ifol;
  vector<Rule*>::iterator ir, ir2;
  vector<Token*>::iterator it;  
  vector<Rule*> r;
  //  bool cont = false;
  bool changed = false;

  //  cout << "\nStarting First To Follow";
  for(ir = rules.begin(); ir != rules.end(); ir++){//for each rule in this
    for(it = (*ir)->first.begin(); it != (*ir)->first.end(); it++){//each token "it" in first of "ir"
      if(!((*it) == (*it)->get_grammar()->get_epsilon())){//Don't copy eps
	if((ifol = nt->follow.find(*it)) != nt->follow.end()){
	  if(!nt->token_pair_in_follow(*it,*ir)){
	    cout << "\nAdded rule. changed = true";
	    changed = true;
	    (*ifol).second.push_back(*ir);
	  }
	}else{
	  changed = true;
	  nt->follow[*it].push_back(*ir);
	}
      }
    }
  }
  return changed;
}

//Copy follow of this to nt; return true if anything added
bool Nonterminal::follow_to_follow(Nonterminal *nt){
  //map<Token*, vector<Rule*> >::iterator im;
  map<Token*, vector<Rule*> >::iterator ifol;
  vector<Rule*>::iterator ir, ir2;
  vector<Rule*> r;
  bool changed = false;

  cout << "\nFollow To Follow";
  for(ifol = follow.begin(); ifol != follow.end(); ifol++){
    for(ir = (*ifol).second.begin(); ir != (*ifol).second.end(); ir++){
      if(!(nt->token_pair_in_follow((*ifol).first, *ir))){
	nt->follow[(*ifol).first].push_back(*ir);
	changed = true;
      }
    }
  }
  return changed;
}

//Copies Token*, vector<Rule*> pairs over from follow set to predict set
void Nonterminal::follow_to_predict(){
  map<Token*, vector<Rule*> >::iterator it; //iterates over follow
  vector<Rule*>::iterator ir; //iterates over the rules in follow
  for(it = follow.begin(); it != follow.end(); it++){
    for(ir = (*it).second.begin(); ir != (*it).second.end(); ir++){
      if(!(this->token_pair_in_predict((*it).first, *ir))){
	predict[(*it).first].push_back(*ir);
	cout << "\nADDED (" << (*it).first->get_name() << " , " << this->get_name() << ") to predict " << this->get_name();
      }
    }
  }
}

void Nonterminal::predict_to_table(Grammar *g){
  //For each terminal, copy the predict mapped rule vector from predict
  //Make sure to access each terminal
  map<string, Terminal*>::iterator it;
  vector<Rule*>::iterator ir;
  vector<Rule*> *r, *r_pred;
  for(it = g->terminals.begin(); it != g->terminals.end(); it++){
    r = &(g->table[this][(*it).second]);
    r_pred = &(predict[(*it).second]);
    for(ir = r_pred->begin(); ir != r_pred->end(); ir++){
      r->push_back(*ir);
    }
  }
}

void Nonterminal::print_first(){
  vector<Rule*>::iterator ir;
  vector<Token*>::iterator it;
  cout << endl << this->get_name();
  for(ir = rules.begin(); ir != rules.end(); ir++){
    for(it = (*ir)->first.begin(); it != (*ir)->first.end(); it++){
      cout << ", " << (*it)->get_name();
    }
  }
}

void Nonterminal::print_follow(){
  map<Token*, vector<Rule*> >::iterator ir;
  cout << endl << this->get_name();
  for(ir = follow.begin(); ir != follow.end(); ir++){
    cout << ", " << (*ir).first->get_name();
  }
}

void Nonterminal::print_predict(){
  map<Token*, vector<Rule*> >::iterator ir;
  cout << endl << "Predict of " << this->get_name();
  for(ir = predict.begin(); ir != predict.end(); ir++){
    cout << ", " << (*ir).first->get_name();
  }
}


//Used in construction of first set, copy all non epsilon rules over, return true
//if an epsilon is found in one of the first sets
bool Nonterminal::copy_first(Rule *r){
  bool epsilon = false;
  vector<Rule*>::iterator ir;
  vector<Token*>::iterator it;
  for(ir = rules.begin(); ir != rules.end(); ir++){
    for(it = (*ir)->first.begin(); it != (*ir)->first.end(); it++){
      //      cout << "\nAbout to get_epsilon()";
      if((*it) != ((*it)->get_grammar()->get_epsilon())){
	//	cout << "\nChecking token_in_first";
	if(!(r->token_in_first((*it)))){
	  //	  cout << "\nToken not in first...";
	  //cout << " pushing into first";
	  r->first.push_back(*it);
	}
      }else{
	epsilon = true;
      }
    }
  }
  return epsilon;
}

///////////////////
//Start Rowe's Code
///////////////////

void Grammar::construct_first(){
  
  map<string, Nonterminal*>::iterator in;
  vector<Token*>::iterator t, it;
  vector<Rule*>::iterator ir;
  bool changed = true;
  bool cont = true;
  vector<Rule*> *prod_rules;

  cout << "\nPutting epsilon where it belongs.";
  //TODO: Find better home for the code below
  //Adds epsilon to the needed rules
  for(in = nonterminals.begin(); in != nonterminals.end(); in++){
    for(ir = (*in).second->rules.begin(); ir != (*in).second->rules.end(); ir++){
      if((*ir)->tokens.empty()){
	(*ir)->tokens.push_back(terminals[get_epsilon_name()]);
      }
    }
  }
  //End of code that needs new home

  cout << "\n\nConstructing First Set\n";

  while(changed){
    cout << endl;
    //Check each nonterminal's first set
    for(in = nonterminals.begin(); in != nonterminals.end(); in++){
      //Have to check for each production rule that matches the nonterminal
      prod_rules = &(in->second->rules);
      for(ir = prod_rules->begin(); ir!= prod_rules->end(); ir++){
	//if the nonterminal isn't in the first set, add it
	cont = true;
	if((*ir)->tokens.empty()){
	  //Somehow epsilon didn't get added
	  cout << "\n\nERROR: Empty rule\n\n";
	}else{//Rule has production tokens
	  t = (*ir)->tokens.begin();
	  while((t != (*ir)->tokens.end()) && cont){
	    if((*t)->is_terminal()){
	      //	      cout << "is a terminal";
	      if(!((*in).second->token_in_first(*t))){
		//Added something, so changed
		(*ir)->first.push_back(*t);
		changed = true;
	      }else{
		changed = false;
	      }
	      cont = false;
	    }else{
	      //Nonterminal, copy first set (excluding epsilon) to this first set.
	      //First(*t) contained epsilon, end loop
	      cont = ((Nonterminal*)(*t))->copy_first(*ir);
	    }
	  }
	}
      }
    }
  }
}

void Grammar::construct_follow(){
  bool changed = true;
  map<string, Nonterminal*>::iterator nt;
  map<Token*, vector<Rule*> >::iterator itv;
  vector<Rule*>::iterator ir, rfirst, rfollow;
  vector<Token*>::iterator it, iterm, itok;
  //  vector<Token*>  *vfirst;
  map<Token*, vector<Rule*> > vfollow;//*vfollowx;
  //  vector<Token*> *t;
  //  vector<Rule*> *prod_rules;
  Rule* rule;
  Token *tok;
  bool eps = true;
  Nonterminal *non, *non_itok;
  cout << "\n\nConstructing Follow Set\n";
  int eps_count, needed_eps;
  //The following code assumes NT start only has one rule, and that that
  //$ should be last token in that rule
  rule = (start->rules[0]);
  tok = *(rule->tokens.rbegin());//last token for starting nonterminal == $
  start->follow[tok].push_back(start->rules[0]);  //push t onto follow of start

  while(changed){
    changed = false;
    for(nt = nonterminals.begin(); nt != nonterminals.end(); nt++){
      for(ir = (*nt).second->rules.begin(); ir != (*nt).second->rules.end(); ir++){
	for(it = (*ir)->tokens.begin(); it != (*ir)->tokens.end(); it++){
	  if(!((*it)->is_terminal())){
	    iterm = it;
	    iterm++;
	    eps = false;
	    eps_count = 0;
	    needed_eps = 0;
	    for(iterm = iterm; iterm != (*ir)->tokens.end(); iterm++){
	      if(!((*iterm)->is_terminal())){
		needed_eps++;
		non = (Nonterminal*)*it;
		non_itok = (Nonterminal*)*iterm;
		changed = non_itok->first_to_follow(non);
		if(non->token_in_first(non->get_grammar()->get_epsilon())){
		  eps_count++; 
		  if(!eps){
		    eps = true;
		  }
		}
	      }
	      if(eps && (eps_count == needed_eps)){
		changed = (*nt).second->follow_to_follow(non);
	      }
	    }
	  }
	}
      }
    }
  }
}		 



/*


  while(changed){
    changed = false;
    //Repeat until no more changes
    for(nt = nonterminals.begin(); nt != nonterminals.end(); nt++){
      //For each nonterminal that isn't %START
      vfollow = ((*nt).second->follow);//Current follow set
      if((*nt).second != start){//Check to make sure isn't %START
	prod_rules = &((*nt).second->rules);
	for(r = prod_rules->begin(); r != prod_rules->end(); r++){
	  //For each production rule
	  t = &((*r)->tokens);
	  for(itok = t->begin(); itok != t->end(); itok++){
	    //For each token itok in the production rule
	    if(!((*itok)->is_terminal())){
	      //If a nonterminal token
	      //TODO, go over tokens after this (use it)
	      it = itok;
	      eps = true;
	      it++;
	      while((!eps) && (it != t->end())){
      		non = (Nonterminal*)*it;
		non_itok = (Nonterminal*)*itok;
		eps = non->token_in_first(non->get_grammar()->get_epsilon());
		changed = non->first_to_follow(non_itok);
		if(eps){
		  changed = (*nt).second->follow_to_follow(non_itok);
		}
		it++;
	      }
	    }else{
	      //Token is nonterminal, add to the follow set
	      if((*nt).second->token_in_follow(*itok)){
		changed = false;
	      }else{
		vfollow[*itok].push_back(*r);
		changed = true;
	      }
	    }
	  }
	}
      }
    }
  }
}
*/
void Grammar::construct_predict(){

  map<string, Nonterminal*>::iterator nt;
  vector<Rule*>::iterator ir;
  vector<Token*>::iterator it, ifirst;
  vector<Token*> t, vfirst, pred, vfollow;
  vector<Rule*> prod_rules;
  bool epsilon = false;
  
  for(nt = nonterminals.begin(); nt != nonterminals.end(); nt++){
    (*nt).second->predict.clear();
  }


  cout << "\n\nConstructing Predict Set\n";
  int eps_count, needed_eps;
  for(nt = nonterminals.begin(); nt != nonterminals.end(); nt++){
    //For each nonterminal in grammar
    //For each production rule, copy tokens of first to predict
    //If first is empty, copy follow set of current nt to predict
    eps_count = 0;
    needed_eps = 0;
    for(ir = (*nt).second->rules.begin(); ir != (*nt).second->rules.end(); ir++){
      needed_eps++;
      (*ir)->first_to_predict((*nt).second);
      if((*ir)->token_in_first((*nt).second->get_grammar()->get_epsilon())){
	epsilon = true;
	eps_count++;
      }
    }
    if(epsilon && (needed_eps == eps_count)){
      (*nt).second->follow_to_predict();
    }
  }
}

void Grammar::construct_table(){
  map<string, Nonterminal*>::iterator in;
  for(in = nonterminals.begin(); in != nonterminals.end(); in++){
    (*in).second->predict_to_table(this);
  }  
}

void Grammar::print_table_to_file(){

  ofstream file;
  map<string, Nonterminal*>::iterator in;
  map<string, Terminal*>::iterator it;
  vector<Rule*>::iterator ir;
  vector<Token*>::iterator ivt;
  vector<Rule*> *r;
  file.open("table.pt");

  //Want output to be of form
  //<N> T: (all tokens in rule)
  //Wrap all N in braces, leave T without

  for(in = nonterminals.begin(); in != nonterminals.end(); in++){
    for(it = terminals.begin(); it != terminals.end(); it++){
      //Access table[nt][t]
      if(!(((*it).second) == ((*in).second->get_grammar()->get_epsilon()))){
	r = &(table[(*in).second][(*it).second]);
	for(ir = r->begin(); ir != r->end(); ir++){
	  file << "<" << (*in).second->name << "> "; //
	  file << (*it).second->get_name() << " :";
	  for(ivt = (*ir)->tokens.begin(); ivt != (*ir)->tokens.end(); ivt++){
	    if((*ivt)->is_terminal()){
	      file << " " << (*ivt)->get_name();
	    }else{
	      file << " <" << (*ivt)->get_name() << ">";
	    }
	  }
	  file << endl;
	}
      }
    }
  }
}
//TODO, fill in all debug and processing functions
void Grammar::assemble(){

  construct_first();
  construct_follow();
  construct_predict();

  debug();  

  construct_table();
  print_table_to_file(); 


}

//TODO: print first, follow, predict
void Grammar::debug(){
  map<string, Nonterminal*>::iterator in;

  cout << endl << endl << "PRINTING FIRST SETS\n";
  for(in = nonterminals.begin(); in != nonterminals.end(); in++){
    (*in).second->print_first();
  }

  cout << endl << endl << "PRINTING FOLLOW SETS\n";
  for(in = nonterminals.begin(); in != nonterminals.end(); in++){
    (*in).second->print_follow();
  }

  cout << endl << endl << "PRINTING PREDICT SETS\n";
  for(in = nonterminals.begin(); in != nonterminals.end(); in++){
    (*in).second->print_predict();
  }
}
/////////////////
//End Rowe's Code
/////////////////

void GrammarParser::expect(const string &str) {
  string read = "";
  for (size_t i = 0; i < str.size(); i++) {
    int c = in->get();
    if (c == -1) {
      throw ParseGrammarException("EOF reached, looking for '" + str + "'");
    }
    read += c;
    if (c != str[i]) {
      cout << "expecting " << str << ". got '" << read << "' instead.";
      throw ParseGrammarException("");
    }
  }
}

void GrammarParser::skip_ws() {
  while (*in && in->peek() == ' ')
    in->get();
}

void GrammarParser::skip_newline() {
  skip_ws();
  expect("\n");
}

string GrammarParser::read_nonterminal_id() {
  expect("<");
  string id = "";
  while (in->peek() != '>')
    id += in->get();
  in->get(); // Consume >
  return id;
}

string GrammarParser::read_terminal_id() {
  string id = "";
  while (in->peek() != '<' && 
        in->peek() != ' ' && 
        in->peek() != '|' && 
        in->peek() != '\n')
    id += in->get();
    
  // cout << "read_terminal_id(): " << id << endl;
  return id;
}

void GrammarParser::parse_tokens() {
  expect("%Tokens");
  string line;
  getline(*in, line);
  
  // cout << "parse_tokens(): read line: '" << line << "'" << endl;
  g.terminals[g.get_epsilon_name()] = new Terminal(&g, g.get_epsilon_name());


  istringstream iss(line);
  string terminal_name;
  iss >> terminal_name;
  while (iss) {
    // TerminalType tt = TerminalType::find(terminal);
    cout << "terminal: '" << terminal_name << "'" << endl;
    g.terminals[terminal_name] = new Terminal(&g, terminal_name);
    iss >> terminal_name;
  }
  // copy(istream_iterator<string>(iss),
  //     istream_iterator<string>(),
  //     back_inserter<vector<string> >(g.terminals));
}

void GrammarParser::parse_nonterminals() {
  expect("%Non-terminals");
  string line;
  getline(*in, line);
  
  istringstream iss(line);
  string nonterminal;
  iss >> nonterminal;
  while (iss) {
    nonterminal = nonterminal.substr(1, nonterminal.size() - 2);
    cout << "nonterminal: '" << nonterminal << "'" << endl;
    g.nonterminals[nonterminal] = new Nonterminal(&g, nonterminal);
    iss >> nonterminal;
  }
}

void GrammarParser::parse_start() {
  expect("%Start");
  
  // Skip WS.
  skip_ws();
  string start_name = read_nonterminal_id();
  
  // Consume rest of line.
  skip_newline();
  
  g.start = g.nonterminals[start_name];
  assert(g.start);

  cout << "Start symbol is '" << start_name << "'." << endl;
}

void GrammarParser::parse_rules_intro() {
  expect("%Rules");
  skip_newline();
}

void GrammarParser::parse_rule_line() {
  string terminal_id;
  string nonterminal_id;
  Nonterminal *nonterminal = NULL;
  Terminal *terminal = NULL;
  int c;
  
  string rule_name = read_nonterminal_id();
  cout << "Reading rule '" << rule_name << "'" << endl;
  Nonterminal *rule_nonterminal = g.nonterminals[rule_name];
  assert(rule_nonterminal);
  
  
  // Create the Rule object and read tokens into it.
  Rule *rule = new Rule(&g, rule_nonterminal); // Adds itself to its nonterminal.
  
  skip_ws();

  expect(":");
  
  skip_ws();
  
  while (*in) {
    switch (in->peek()) {
        case '\n':
        // We're done, just return.
        // cout << "done reading " << rule_name << endl;
        c = in->get(); // Consume newline.
        // cout << "read '" << c << "' btw" << endl;
        return;
        break;
    
        case '<':
        nonterminal_id = read_nonterminal_id();
        nonterminal = g.nonterminals[nonterminal_id];
        // cout << "read nonterminal <" << nonterminal_id << ">" << endl;
        assert(nonterminal);
        rule->tokens.push_back(nonterminal);
        break;
    
        case '|':
        // Start a new rule.
        // cout << "start a new rule" << endl;
        in->get(); // Consume |.
        rule = new Rule(&g, rule_nonterminal);
        break;
    
        default:
        terminal_id = read_terminal_id();
        terminal = g.terminals[terminal_id];
        cout << "read terminal " << terminal->get_name() << endl;
        assert(terminal);
        rule->tokens.push_back(terminal);
    }
    skip_ws();
  }
  
}

GrammarParser::GrammarParser() {
  in = NULL;
}

void GrammarParser::parse(istream *in) {
  this->in = in;
  
  try {
    parse_tokens();
    parse_nonterminals(); 
    parse_start(); 
    parse_rules_intro(); 
    
    while (*in) {
      
      parse_rule_line();
      skip_ws();
      
      in->peek(); // Makes the loop work for some reason...

    }

    //g.print_rules();
    
    cout << "Done." << endl;
    //cout << "RLR: Start remove_left_recursion()" << endl;
    g.remove_left_recursion();
    g.create_left_factoring();
    //cout << "RLR: End remove_left_recursion()" << endl;
    
    g.construct_table();
    g.print_table_to_file();

    g.print_rules();
    
  } catch (const ParseGrammarException &whoops) {
    cout << "exception: " << whoops.get_why() << endl;
  }
}

int main(int argc, const char *argv[]) {
  
  if (argc != 2) {
    cout << "usage: grammar foo.grammar" << endl;
    return 1;
  }
  
  GrammarParser gp;
  ifstream in(argv[1]);
  
  gp.parse(&in);
  (gp.get_g()).assemble();

  cout << endl;
  
  return 0;
}
